//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
package codeRandomThoughts.Test17电话号码的字母组合;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    private StringBuilder path = new StringBuilder();
    private List<String> result = new ArrayList<>();

    private String[] numMap = {
            "",//0
            "",//1
            "abc",//2
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()){
            return result;
        }
        char[] chars = digits.toCharArray();
        backtracking(chars, 0);
        return result;
    }

    public void backtracking(char[] chars, int startIndex) {
        //回溯终止条件
        if (startIndex >= chars.length) {
            result.add(path.toString());
            return;
        }

        //单层回溯逻辑
        //获取本层要遍历的字母集合
        int num = chars[startIndex] - '0';
        char[] letters = numMap[num].toCharArray();
        for (int i = 0; i < letters.length; i++) {
            path.append(letters[i]);
            backtracking(chars, startIndex + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
